//
//  BinaryNode.swift
//  Chapter3LinkedList
//
//  Created by TRS-Mobile on 2021/9/1.
//

import Foundation

class BinaryNode<E> {
    var value: E
    var leftChild: BinaryNode?
    var rightChild: BinaryNode?
    init(value: E) {
        self.value = value
    }
}

extension BinaryNode {
    
    /// 中序遍历
    /// - Parameter visit: visit description
    /// - Returns: description
    func  traverseInOrder(visit: (E) -> Void) -> Void {
        leftChild?.traverseInOrder(visit: visit)
        visit(value)
        rightChild?.traverseInOrder(visit: visit)
    }
    
    func traversePreOrder(visit: (E) -> Void) -> Void {
        visit(value)
        leftChild?.traversePreOrder(visit: visit)
        rightChild?.traversePreOrder(visit: visit)
    }
    
    func traversePostOrder(visit: (E) -> Void) -> Void {
        leftChild?.traversePostOrder(visit: visit)
        rightChild?.traversePostOrder(visit: visit)
        visit(value)
    }
}

extension BinaryNode: CustomStringConvertible {
    var description: String {
        return diagram(for: self)
    }
    
    private func diagram(for node: BinaryNode?,
                         _ top: String = "",
                         _ root: String = "",
                         _ bottom: String = "") -> String
    {
        guard let node = node else { return root + "nil\n" }
        if node.leftChild == nil && node.rightChild == nil {
            return root + "\(node.value)\n"
        }
        return diagram(for: node.rightChild, top + " ", top + "┌──", top + "│ ")
            + root + "\(node.value)\n"
            + diagram(for: node.leftChild, bottom + "│ ",  bottom + "└──",  bottom + " ")
    }
}

extension BinaryNode {
    var min: BinaryNode {
        return leftChild?.min ?? self
    }
}
